%!TEX program = xelatex
\documentclass[lang=cn,11pt,a4paper,citestyle =authoryear]{elegantpaper}

% 标题
\title{数值分析项目作业实验报告}
\author{强基数学2001 \\ 关博仁}
\date{\zhtoday}


% 本文档命令
\usepackage{array,url}
\usepackage{subfigure}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}


% 文档区
\begin{document}

% 标题
\maketitle

%摘要
\begin{abstract}
本文为浙江大学2022-2023秋冬学期王何宇老师的《数值分析》课程作业，
内容为《数值分析 张庆海》第三章编程作业暨项目作业，代码将会上传到仓库\href{https://gitee.com/wellsguan/na2022.git}{na2002}。
\end{abstract}

\section{实验设计思路}
本次项目作业主要是实现\code{ppForm}和\code{B}两种样条模型，支持不同的边界条件和输入，很自然的想到针对每种输入都进行一个封装，在此之前建立一个公共的基类，包含公共方法，便于后期针对不同的子类进行统一的调用：
\begin{lstlisting}
class SplineBase{
public:
    bool _is_increasing(vector<double> x);
    // 用于判断输入是否递增
    SplineBase(){}
    ~SplineBase(){}
    virtual double operator () (double x);
    // 用于输出样条映射下x的映射值
};
\end{lstlisting}
对于输入，我们预期添加如下的接口：
\begin{itemize}
    \item 立方样条类(函数输入): vector<double> 结点,func\& 函数,int 边界条件
    \item 立方样条类(散点插值): vector<double> 结点,vector<double> 函数值
    \item 立方样条类(二维曲线拟合)：vector<double> x, vector<double> y
\end{itemize}
输入标准很单一，只要求输入的结点是递增的即合法，对于曲线拟合没有特别要求，输入边界条件分别是完全立方样条、边界二阶导数拟合、自然立方样条，散点插值默认是自然立方样条的边界条件。\par
这三个封装的思考是自然的递进过程，散点插值通过特征函数映射构造的函数输入样条进行生成，二维曲线拟合通过两次散点插值进行生成，具体实现参见源代码。前两者分别有可用方法：\code{Object()}和\code{Object.copy()}，用来输出映射值和深度拷贝。更多的具体细节可以参见我的源代码中的注释。\par
对线性插值，两种算法没有区别，序列输入和函数输入容易转化，故仅提供一种实现,参数如下：
\begin{lstlisting}
Linear_Spline(vector<double> knots, vector<double> values)
\end{lstlisting}
使用C题例子进行测试，有如下结果：
\begin{figure}[htbp]
    \centering
    \subfigure[]
    {\includegraphics[width = 0.48\textwidth]{../png/Linear_test_1.png}}
    \subfigure[]
    {\includegraphics[width = 0.48\textwidth]{../png/Linear_test_2.png}}
\end{figure}
可见实现可靠，方法正确。

\section{编程题目实现}

\subsection{题目A}
本题目中我们使用自然立方样条算法，分别实现并绘图如下：
\begin{figure}[htbp]
    \centering
    \subfigure[N=6]
    {\includegraphics[width = 0.3\textwidth]{../png/SplinesA_6.png}}
    \subfigure[N=11]
    {\includegraphics[width = 0.3\textwidth]{../png/SplinesA_11.png}}
    \subfigure[N=21]
    {\includegraphics[width = 0.3\textwidth]{../png/SplinesA_21.png}}
\end{figure}
\begin{figure}[htbp]
    \centering
    \subfigure[N=41]
    {\includegraphics[width = 0.3\textwidth]{../png/SplinesA_41.png}}
    \subfigure[N=81]
    {\includegraphics[width = 0.3\textwidth]{../png/SplinesA_81.png}}
\end{figure}

很明显Runge现象是被消除了的，我们接下来其他的误差，得到输出：
\begin{lstlisting}
The maxnorm is 0.128924 when N equals 6.
The maxnorm is 0.0841293 when N equals 11.
The maxnorm is 0.00805262 when N equals 21.
The maxnorm is 0.000341762 when N equals 41.
The maxnorm is 1.62997e-05 when N equals 81.
\end{lstlisting}
对$N^{-k}$进行标准化并绘图如下：
\begin{figure}[htbp]
    \centering
    \includegraphics[width = 0.5\textwidth]{../png/SplinesA_Log.png}
\end{figure}
根据图像认为散点与$C\cdot N^{-2}$，认为收敛阶为2。

\subsection{题目B}
参见源代码中B样条实现部分。

\subsection{题目C}
笔者在处理本题时遇到了一些问题，在设计BSpline时取巧仅设计了对于函数在正整数点的插值，但是很容易发现，这不影响我们的进行，事实上任何间隔为整数点的插值只需要通过对待插值映射进行平移变换就可以得到正整数点处的插值，在这个思路上，我们直接将待插值函数进行平移即可实现，有下面结果：
\begin{figure}[htbp]
    \centering
    \subfigure[Cubic]
    {\includegraphics[width = 0.45\textwidth]{../png/BSplines_cubic.png}}
    \subfigure[Quadratic]
    {\includegraphics[width = 0.45\textwidth]{../png/BSplines_quad.png}}
\end{figure}
同样的，我们得到了很好的拟合效果。

\subsection{题目D}
为了判定两个样条的精确度，我们对所给的点的误差进行求和并比较，得出如下结果：
\begin{lstlisting}
---- x ----|----- quad_err -----|----- cubic_err -----|
  -3.500000|           +0.000000|            +0.000670|
  -3.000000|           +0.001418|            +0.000000|
  -0.500000|           +0.000000|            +0.020529|
  +0.000000|           +0.120237|            +0.000000|
  +0.500000|           +0.000000|            +0.020529|
  +3.000000|           +0.001341|            +0.000000|
  +3.500000|           +0.000000|            +0.000670|
The sums of error are respectively 0.122997 and 0.0423969.
\end{lstlisting}
从结果来看，对于题目所给函数的拟合，立方B样条的准确率更高，符合我们的期望。下面讨论一些结果趋近于机器精度的原因。\par
事实上，很容易看出所选择的点当中有部分是两个样条构造时的结点，并且结点交替出现，以0.5为间隔，因此在这些点上，样条理论上是不存在误差的，于是计算的结果小于机器误差。\par
此外，直接对上面的点处误差求和来比较并不准确，对上面的值求其关于不为0的个数的平均值是更正确的选择，但显然在本次的输出中即使平方B样条的非零项更少，但却取得更大的误差和，故不影响我们的结论。\par

\subsection{题目E}
观察爱心方程：
\[x^2+(\dfrac{3}{2}y-\sqrt{|x|})^2 = 3\]
可见$x\in[-\sqrt{3},\sqrt{3}]$，并且对于$x^2<3$，有两个$y$值与其对应，考虑到机器精度，可以考虑直接取等距离的若干$x$值对应的若干组点对进行排序后的插值，具体实现参见源代码，有如下结果：
\begin{figure}[htbp]
    \centering
    \subfigure[N=10]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_10.png}}
    \subfigure[N=40]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_40.png}}
    \subfigure[N=160]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_160.png}}
\end{figure}\par
事实上，效果一般，考虑边界条件，我们使用的是自然立方样条进行拟合，考虑到曲线拟合并不能提供局部特征，立方样条让数据自行决定了端点处的导数，而且我们无法通过其他已有的样条算法对此进行优化，所以确定端点是一个可能的好的优化角度，将端点设为0处，有如下结果。\newpage
\begin{figure}[htbp]
    \centering
    \subfigure[N=10]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_OPT_10.png}}
    \subfigure[N=40]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_OPT_40.png}}
    \subfigure[N=160]
    {\includegraphics[width = 0.3\textwidth]{../png/HeartPlot_OPT_160.png}}
\end{figure}
可见拟合效果显著提升，猜想正确。

\end{document}
